package test;

//从前序和中序遍历序列中构造二叉树
//给定两个整数数组 preorder 和 inorder ，
// 其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点



public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {

      }
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder , 0 ,inorder.length - 1) ;
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        //这种情况下表明当前root没有子树了
        if(inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findVal(inorder , inbegin,inend , preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder , inorder ,inbegin ,rootIndex - 1);
        root.right = buildTreeChild(preorder , inorder ,rootIndex +1 ,inend);
        return root;
    }

    private int findVal(int[] inorder , int inbegin , int inend , int val){

        for(int i = inbegin;i <= inend ; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }
}